# my first solution, O(n)

import sys

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        length = len(ratings)
        if length==0: return 0
        trends = []
        last = ratings[0]
        for r in ratings[1:]:
            if r>last:
                trends.append(1)
            elif r<last:
                trends.append(-1)
            else:
                trends.append(0)
            last=r
        
        last = -1
        vallys = []
        for i, trend in enumerate(trends):
            if trend!=last:
                vallys.append(i)
            last = trend
        if last==-1:
            vallys.append(length-1)
        
        nums = [1] * len(ratings)
        for vally in vallys:
            for i in range(vally, length-1):
                if trends[i]==1:
                    nums[i+1]=max(nums[i]+1, nums[i+1])
                else:
                    break
            for i in range(vally)[::-1]:
                if trends[i]==-1:
                    nums[i]=max(nums[i+1]+1, nums[i])
                else:
                    break
        
        return sum(nums)

print(Solution().candy([5,1,1,1,10,2,1,1,1,3]))